#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

template<size_t N=0xFFFFFFFF>
class Bit 
{
public: 
	Bit()
	{
		//初始化，只需要给数组开辟空间并初始化为0
		_bits.resize(N/8+1,0);//大小是多少?如果不给定数据范围为无符号整形，可以使用模板参数，+1是因为不一定整除
	}
	void set(size_t x)//对于传入的无符号整形数据，set()将对应bit位置为1
	{
		size_t pos=x/8; size_t offset=x%8;
		_bits[pos]|=1<<offset;
	}
	void reset(size_t x)//对于传入的无符号整形数据，set()将对应bit位置为0
	{
		size_t pos=x/8; size_t offset=x%8;
		_bits[pos]&= ~(1<<offset);
	}
	bool judge(size_t x)//对于传入的无符号整形数据，判断其是否存在 
	{
		size_t pos=x/8; size_t offset=x%8;
		return _bits[pos]&(1<<offset);
	}
  size_t size()
  {
    return _bits.size();
  }
	
private:
	vector<char> _bits;
};

void TestIn()
{
  Bit<> bs;
  cout<<bs.size()<<endl;
  bs.set(100);
  bs.set(1024*1024-100);
  bs.set(1024*512-50);
  cout<<bs.judge(100)<<endl;
  cout<<bs.judge(1024*1024-100)<<endl;
  cout<<bs.judge(1024*512-50)<<endl;
  cout<<bs.judge(10)<<endl;
  cout<<bs.judge(1000)<<endl;
  cout<<bs.judge(20)<<endl;

  bs.reset(1024*1024-100);
  cout<<bs.judge(1024*1024-100)<<endl;

  //
}

template<size_t N=0xFFFFFFFF>
class TwoBits
{
public:
	void set(size_t x)
	{
		int bit1=_bt1.judge(x);//默认小数字为高位
		int bit2=_bt2.judge(x);
		if(bit2==0)
			_bt2.set(x);
		else if(bit1==0)
			_bt1.set(x);
	}
//	void unset(size_t x)//无法做到unset
//	{
//		int bit1=_bt1.judge(x);
//		int bit2=_bt2.judge(x);
//	}
	bool judge(size_t x)
	{
		return _bt2.judge(x) && (!_bt1.judge(x));
	}
private:
	Bit<N> _bt1;
	Bit<N> _bt2;
};

void TestIsOnce()
{
  TwoBits<> tbs;
  for(size_t i=0;i<10;++i)
  {
    tbs.set(i);
  }
  for(size_t i=0;i<10;i+=2)
  {
    tbs.set(i);
  }
  for(size_t i=0;i<10;++i)
  {
    if(i%3==0)
      tbs.set(i);
  }
  for(size_t i=0;i<15;++i)
  {
    cout<<tbs.judge(i)<<endl;
  }

}

/*3.给定两个文件，分别有100亿个整数，给点1G的内存，如何找到两个文件交集?
BitSet做到了对数据的存储吗？实际上做到了!因为 实际数据->bit位 之间存在映射关系，可以通过bit位得到数据值
因此思路是:对于每个文件，使用BitSet位图进行映射判断其是否存在(100亿个bit位)，然后按位与这100亿个bit位，再按位读出数据值*/
template<size_t N=100>//范围0~99
class intersection
{
public:
	void input1(size_t x)
	{
		_bt1.set(x);
	}
	void input2(size_t x)
	{
		_bt2.set(x);
	}
	void overlap()
	{
		for(size_t i=0;i<N;++i)
		{
			if(_bt1.judge(i) && _bt2.judge(i))
				_retBit.set(i);
		}
	}
	void retPrint()
	{
		for(size_t i=0;i<N;++i)
		{
			if(_retBit.judge(i))
				cout<<i<<" ";
		}
		cout<<endl;
	}
private:
	Bit<N> _bt1;
	Bit<N> _bt2;
	Bit<N> _retBit;
};

void TestOverlap()
{
	intersection<> inter;
	for(size_t i=1;i<100;++i)
	{
    if(i%2==0)
		  inter.input1(i);
	}
	for(size_t i=1;i<100;++i)
	{
    if(i%3==0)
		  inter.input2(i);
	}
  inter.overlap();
	inter.retPrint();
}

//4.位图应用的变形:1个文件有100亿个int，1G的内存，设计算法找到次数不超过2次的所有整数 同问题2

//5.布隆过滤器
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};


struct JSHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 1315423911;
		for (auto ch : s)
		{
			hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
};

template<size_t M,class K=string,class HashFunc1=BKDRHash,class HashFunc2=APHash,class HashFunc3=DJBHash>
class BloomFilter
{
public:
	void Set(const K& ip)
	{
		size_t pos1=HashFunc1()(ip)%M;
		size_t pos2=HashFunc2()(ip)%M;
		size_t pos3=HashFunc3()(ip)%M;
		_bt.set(pos1);
		_bt.set(pos2);
		_bt.set(pos3);
	}
	
	bool Judge(const K& ip)
	{
		size_t pos1=HashFunc1()(ip)%M;
		size_t pos2=HashFunc2()(ip)%M;
		size_t pos3=HashFunc3()(ip)%M;
		return _bt.judge(pos1)&&_bt.judge(pos2)&&_bt.judge(pos3);
	}
	
private:
	Bit<M> _bt;
};

void TestBloomFilter()
{
	//m=-n*ln(exp)  /  (ln2)^2
	//假设允许误差为exp=0.005，数据个数n=10,计算得m为110左右
	const size_t N=1000000;
	BloomFilter<N*11> bf;
	vector<string> str_arr;
	for(size_t i=0;i<N;++i)
	{
		string str="后藤"+to_string(i)+"里";
		bf.Set(str);
		str_arr.push_back(str);
	}
	for(size_t i=0;i<N;++i)
	{
		string str="后藤"+to_string(N+i)+"里";
		str_arr.push_back(str);
	}
	//一共2*N个数据，现计算出现误判的数据
	size_t misnum=0;
  for(size_t i=0;i<2*N;++i)
  {
		if(i<N && bf.Judge(str_arr[i])==false)
			++misnum;
		else if(i>=N && bf.Judge(str_arr[i])==true)
			++misnum;
  }
	cout<<"误判率:"<<misnum*1.0/(N*2)<<endl;
	
}

//6.哈希切割的思想
/*哈希切割
场景:给定一个超过100GB的logfile，找到出现次数最多的IP和TopK的IP。
难点:位图结构只适用于key模型，而map虽然适用于KV模型，但直接存储IP地址空间消耗又极大(无法承担)。
思路:将大文件切分成小文件，然后对小文件的数据使用map进行次数统计。但是存在问题:同一个ip可能分布在不同的文件里，因此统计结果也要在内存中存储起来待最终处理(加和)。由于统计结果也要存储，
与原本相比，本质只实现了'去重'。但是如果ip极其分散，也即重复的ip并不多，去重并不能明显缩小数据量，则行不通了。
因此提出'哈希切割':利用哈希映射的唯一性，可以确保相同的ip一定映射到同一个文件中，而不同ip映射到不同的文件又可以做到'切割'。因此只要对小文件进行次数统计，找到其出现次数最多的IP和TopK的IP
然后将切割成的不同小文件的次数最多ip对比，找出所有文件次数最多的ip即可。
如果出现hash拥堵的情况，即可能部分划分的小文件也非常的大，无法使用map进行统计，则考虑多次哈希切割，即
try
{
	//对文件进行次数统计
}
catch
{
	//捕获到异常，则再次进行hash切割，即使用不同的hash函数，对小文件进行哈希切割
}
*/
/*
哈希切割其他应用:
1.给定两个文件，分别存有100亿个query(string)。给定1GB内存，如何设计算法找到交集?分别给出近似算法和精确算法。
近似算法:布隆过滤器
精确算法:
哈希切割[1],形成小文件后，如果小文件足够小，则可以使用set取交集，否则继续切割。
*/
